#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int key;
    int value;
    struct Node *left;
    struct Node *right;
    int height;
} Node;

Node *createNode(int key, int value){
    Node *node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->left = node->right = NULL;
    node->height = 1; // 节点创建默认高度为1
    return node;
}

int height(Node *node){
    if(node){
        return node->height;
    }else{
        return 0;
    }
}

void upheight(Node *node){
    if(node){
        node->height = 1 + (height(node->left)>height(node->right) ? height(node->left): height(node->right));
    }
}

Node *leftRetate(Node *node){
    Node *temp = node->right;
    node->right = temp->left;
    temp->left = node;
    upheight(node);
    upheight(temp);
    return temp;
}
Node *rightRetate(Node *node){
    Node *temp = node->left;
    node->left = temp->right;
    temp->right = node;
    upheight(node);
    upheight(temp);
    return temp;
}

// 平衡因素计算（左 减 右）
int balanceFactor(Node *node){
    return height(node->left)-height(node->right);
}

// 插入，这里用Node用来返回平衡后的二叉树
Node *insert(Node *node, int key, int value){
    if(node == NULL){
        node = createNode(key,value);
        return node;
    }
    if(key<node->key){
        node->left = insert(node->left,key,value);
    }else if(key>node->key){
        node->right = insert(node->right,key,value);
    }else{
        node->value = value; // 该键已经存在，更新值
        return node; 
    }
    // 更新节点的高度
    upheight(node);
    // 计算平衡因素
    int bf = balanceFactor(node);
    
    if(bf>1){
        if(key < node->left->key){ // LL型，右旋
            return rightRetate(node);
        }else{ // LR型，先左旋再右旋
            node->left = leftRetate(node->left);
            return rightRetate(node);
        }
    }else if(bf<-1){
        if(key > node->right->key){ // RR型，左旋
            return leftRetate(node);
        }else{ // RL型，先右旋再左旋
            node->left = rightRetate(node->left);
            return leftRetate(node);
        }
    }
    return node;
}

// 找到树中最小的节点
Node* findMin(Node* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

// 删除节点
Node* deleteNode(Node* root, int key) {
    if (root == NULL) {
        return root;  
    }

    if (key < root->key) {
        root->left = deleteNode(root->left, key);  // 删除左子树中的节点
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key); // 删除右子树中的节点
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;  // 返回右子树
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;  // 返回左子树
        } else {
            // 节点有两个子节点，找到右子树中的最小节点
            Node* temp = findMin(root->right);

            // 用右子树最小节点的值替换当前节点
            root->key = temp->key;

            // 删除右子树中的最小节点
            root->right = deleteNode(root->right, temp->key);
        }
    }

    // 更新当前节点的高度
    upheight(root);

    // 检查当前节点的平衡因子
    int balanceFactor = getBalanceFactor(root);

    // 如果节点不平衡，执行相应的旋转操作

    // 左左（LL）情况
    if (balanceFactor > 1 && getBalanceFactor(root->left) >= 0) {
        return rightRotate(root);
    }

    // 右右（RR）情况
    if (balanceFactor < -1 && getBalanceFactor(root->right) <= 0) {
        return leftRotate(root);
    }

    // 左右（LR）情况
    if (balanceFactor > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // 右左（RL）情况
    if (balanceFactor < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

// 中序遍历打印AVL树
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->key);
        inorderTraversal(root->right);
    }
}

// 打印树的结构
void printTree(Node* root, int space) {
    if (root == NULL) {
        return;
    }

    space += 10; // 设置间隔宽度

    // 先打印右子树
    printTree(root->right, space);

    // 打印当前节点
    printf("\n");
    for (int i = 10; i < space; i++) {
        printf(" "); // 添加空格来显示树的深度
    }
    printf("%d\n", root->key);

    // 打印左子树
    printTree(root->left, space);
}

int main(){
    Node *tree = NULL;
    tree = insert(tree,1,10);
    tree = insert(tree,2,20);
    tree = insert(tree,3,30);
    tree = insert(tree,4,40);

    inorderTraversal(tree);
    printf("\n----------root: %d----------\n", tree->key);
    printTree(tree,0);

    return 0;
}